1. Field of the Invention
The present invention relates to an image formation technique that can realize load distribution in image processing.
2. Description of the Related Art
It is conventionally known to perform image formation processing based on the depth of an object included in a scanline, which is referred to as “scanline model”, as one of image formation processing techniques. For example, the image formation processing can be performed on a target page 200 illustrated in FIG. 2 on a line-to-line basis.
More specifically, in a drawing line 201, the image formation processing of a page line 210 indicating a pixel of the page 200, an image line 211 indicating a pixel of an image object 202, and a transmissive monochrome line 212 indicating a pixel of a transmissive monochrome graphic object 203 is performed.
In this case, the image formation processing includes dividing an object on the page 200 into a plurality of closed areas, for example, a closed area “0” 205, a closed area “1” 206, a closed area “2” 207, a closed area “3” 208, and a closed area “4” 209. Each closed area is divided by a contour (hereinafter, referred to as “edge”). Each closed area is a processing target area to be independently subjected to the image formation processing.
Further, the image formation processing performed on each closed area will be described. For example, if the processing target area is the closed area “1” 206 illustrated in FIG. 3, the image formation processing includes performing application information generation processing 312 based on white color information 310, which indicates color information of the page 200, and generating a white pixel 316 that represents a pixel of the page line 210 in the closed area “1” 206.
Further, the image formation processing includes calculation processing 313 for calculating a pixel offset 317 of a read image based on image information 311. The pixel offset calculation to be performed in this case can be realized by affine transformation processing while taking designated rotation, modification, and enlargement/reduction into consideration.
Further, the image formation processing includes acquiring actual pixel information from an offset indicated by the pixel offset 317 to generate an image pixel 318 that represents a pixel of the image line 211 in the closed area “1” 206. As a final process, the image formation processing includes performing composition processing 315 using the white pixel 316 and the image pixel 318 to acquire a closed area “1” pixel 319 that represents a final color value of the closed area “1” 206. The above-described image formation processing is repetitively performed for the remaining closed areas to accomplish the image formation of the page 200.
Further, to improve performance and reduce the cost in image formation processing, a multiprocessor is recently available to realize multi processing technique. In image formation processing, distribution of the processing can be realized by causing a plurality of image formation processing units, such as a first image formation processing unit 400 and a second image formation processing unit 401 illustrated in FIG. 4, to perform predetermined processing.
Further, the multiprocessor is usable to realize the scanline model image formation processing. For example, pixel generation processing 322 including processing 312, processing 313, processing 314) for generating pixels of each object may be allocated to the first image formation processing unit 400. Further, pixel composition processing 323 including the composition processing 315 may be allocated to the second image formation processing unit 401.
As described above, using a plurality of image formation processing units is useful to realize the distribution of the processing. Further, if processing to be allocated to each of a plurality of image formation processing units is determined beforehand, a predetermined CPU-dedicated command capable of increasing the processing speed or expansion of a hardware configuration can be realized by using only one image formation processing unit. As a result, the processing can be speedily accomplished and the cost can be reduced.
Further, as a technique capable of realizing the load distribution among a plurality of image formation processing units, a multiprocessor-based technique discussed in Japanese Patent Application Laid-Open No. 6-274608 includes dividing image formation processing to be performed for each drawing object into a plurality of processing blocks. The conventional technique further includes allocating each divided image formation processing to an optimum image formation processing unit having a relatively light load with reference to the load status of each image formation processing unit.
According to the above-described processing distribution system that allocates predetermined processing to each of a plurality of image formation processing units as illustrated in FIG. 4, the processing load of each image formation processing unit is variable depending on the tendency of data to be processed. The load distribution in image processing may not be realized in an optimum way. For example, if the rotational angle is 0° or 180° as illustrated in FIG. 5, the process of reading pixel data from an image memory area 500 is performed along an arrow 501 for the 0 degree rotation and an arrow 502 for the 180 degree rotation.
In this case, the pixel data acquisition processing 314 to be performed in acquiring a pixel 1 includes accessing the image memory area 500 and loading a predetermined size of pixel data into a cache 512. The probability that the subsequent pixels 2 to 6 are present in the cache is high. Therefore, there is a tendency that the subsequent pixels 2 to 6 are acquirable from the cache 512, i.e., from the data loaded in the process of acquiring the pixel 1.
Therefore, the number of operations repetitively accessing the image memory area 500 can be reduced. It is feasible to perform the pixel generation processing 321 at a relatively higher speed. On the other hand, if the rotational angle is 90° or 270°, the process of reading pixel data from the image memory area 500 is performed along an arrow 503 for the 90 degree rotation and an arrow 504 for the 270 degree rotation.
In this case, the pixel data acquisition processing 314 to be performed in acquiring a pixel 13 includes accessing the image memory area 500 and loading a predetermined size of pixel data in the cache 512. However, in the process of acquiring a pixel 7, the probability that the pixel 7 is included in the predetermined size of pixel data loaded in the cache is low because the pixel 7 is present in an area far from the pixel 13. Accordingly, the probability that the pixel 7 is not present in the cache is high. Therefore, it is required to repeat the processing for loading a predetermined size of pixel data into the cache until the pixel 7 can be acquired.
Processing required to acquire the next pixel 1 is similar to the processing required to acquire the pixel 7. Accordingly, when the rotational angle is 90° or 270°, the cache cannot be effectively used and the number of operations repetitively accessing the image memory area 500 tends to increase. A relatively long time is required to complete the pixel generation processing 321. Further, when the rotational angle is an arbitrary angle other than 0°, 90°, 180°, and 270°, processing to be required in this case tends to be similar to the above-described processing for the 90° or 270° rotation if the arbitrary rotational angle is closer to 90° or 270° than 0° (360°) or 180°. The meaning of “the arbitrary rotation angle is closer to 90° or 270° than 0° (360°) or 180°” is, for example, that the arbitrary rotation angle is larger than 45° and smaller than 135°, or larger than 225° and smaller than 315°. In the present exemplary embodiment, such an angle is referred to as a first type angle. On the other hand, if the arbitrary rotational angle is closer to 0° (360°) or 180° than 90° or 270°, processing to be required in this case tends to be similar to the above-described processing for the 0° or 180° rotation. The meaning of “the arbitrary rotational angle is closer to 0° (360°) or 180° than 90° or 270°” is, for example, that the arbitrary rotation angle is larger than 0° and equal to or smaller than 45°, equal to or larger than 135° and equal to or smaller than 225°, or equal to or larger than 315° and smaller than 360°. In the present exemplary embodiment, such an angle is referred to as a second type angle. In short, the processing load tends to vary depending on the rotational angle.
Further, in the pixel composition processing 322, the processing load in the closed area “0” 205 tends to become lighter because the number of overlapped objects is small, namely because the number of pixels to be subjected to the composition processing is small.
On the other hand, the processing load in the closed area “2” 207 tends to become heavier because the number of overlapped objects is large, namely because the number of pixels to be subjected to the composition processing is large. Further, the processing load tends to vary depending on the contents of a plurality of overlapped objects to be subjected to the composition processing. If the processing to be allocated is determined beforehand, the processing load is variable depending on the difference in rotational angle and the presence of the composition processing.
Further, the conventional technique discussed in Japanese Patent Application Laid-Open No. 6-274608 includes calculating the processing load for each object and performing the load distribution in image processing based on the calculated load amount. However, according to the scanline model image formation processing, the processing load is variable depending on each area even if the target object is the same. From the reasons described above, the conventional technique is unable to appropriately determine the processing load and unable to effectively perform the load distribution.
For example, in a case where a drawing line 601 of a page 600 illustrated in FIG. 6 is drawn, the processing includes dividing a processing target area into a plurality of closed areas illustrated on the right side of FIG. 6. In this case, a transmissive monochrome graphic object 603 straddles a closed area “5” 604 and a closed area “6” 605. Each closed area is subjected to the drawing processing. In this case, the composition processing for a transmissive monochrome line 612 in the closed area “5” 604 is performed based on a combination with an image line 611. Therefore, performing the composition processing for each pixel is required.
On the other hand, the composition processing for the transmissive monochrome line 612 in the closed area “6” 605 is performed based on a combination with a page line 610. Therefore, the composition processing to be performed in this case is simply combining the processing target with the monochrome representing the color of the page. Therefore, regardless of the number of pixels, the realization of the processing requires only one composition processing and a plurality of outputs of the composition result. More specifically, there is a case where considering the dependency on other object in the closed area (e.g., overlap between objects, type of the composition, etc.) is required in the load determination. In this respect, the above-described conventional technique is unable to take the dependency into consideration in the load determination.
Further, the processing order in the scanline model image formation processing is dependent on the drawing processing to be performed for each closed area. Therefore, if the load distribution and the processing are performed on an object-by-object basis, it is unable to maintain optimum performances because the parallelism between respective processing cannot be maintained.
For example, the drawing processing of a drawing line 621 of a page 620 includes dividing a processing target area into a plurality of closed areas illustrated on the right side of FIG. 6. In this case, if the conventional technique is employed to divide the processing on an object-by-object basis, the image formation processing along an image line 631 straddles a closed area “5” 624 and a closed area “6” 625. Accordingly, the processing cannot be accomplished unless the image formation along the image line 631 is thoroughly completed.
Accordingly, the composition processing for combining the image line 631 with a transmissive monochrome line 632 does not start before completing the image formation processing of the image line 631. In other words, it is unable to maintain the parallelism between the image formation and the composition processing. Accordingly, it is desired to provide a load distribution technique that can solve the above-described conventional problems.